#include <bits/stdc++.h>
using namespace std;

/*
3068. 最大节点价值之和
已解答
困难
相关标签
相关企业
提示
给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ，其中 nums[i] 表示节点 i 的 价值 。

Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：

选择连接节点 u 和 v 的边 [u, v] ，并将它们的值更新为：
nums[u] = nums[u] XOR k
nums[v] = nums[v] XOR k
请你返回 Alice 通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。

 

示例 1：



输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：Alice 可以通过一次操作得到最大价值和 6 ：
- 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。
所有节点价值之和为 2 + 2 + 2 = 6 。
6 是可以得到最大的价值之和。
示例 2：



输入：nums = [2,3], k = 7, edges = [[0,1]]
输出：9
解释：Alice 可以通过一次操作得到最大和 9 ：
- 选择边 [0,1] 。nums[0] 变为：2 XOR 7 = 5 ，nums[1] 变为：3 XOR 7 = 4 ，数组 nums 变为：[2,3] -> [5,4] 。
所有节点价值之和为 5 + 4 = 9 。
9 是可以得到最大的价值之和。
示例 3：



输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
输出：42
解释：Alice 不需要执行任何操作，就可以得到最大价值之和 42 。
 

提示：

2 <= n == nums.length <= 2 * 104
1 <= k <= 109
0 <= nums[i] <= 109
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
输入保证 edges 构成一棵合法的树。
*/

// 法一
class Solution {
public:
    using ll = long long;
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        ll total = 0;
        vector<int> deltas;
        for(int num : nums) {
            total += num;
            deltas.push_back((num ^ k) - num);
        }
        // 做个排序 greater 谓词
        sort(deltas.begin(), deltas.end(), greater<int>());

        for (int i = 0; i < deltas.size(); i += 2) {
            if (i + 1 >= deltas.size()) break;
            int sum = deltas[i] + deltas[i + 1];
            if (sum > 0)  total += sum;
            else    break;
        }
        return total;
    }
};

// 法二
class Solution {
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        // 计算nums数组中所有元素的总和，并将结果保存在res变量中
        long long res = accumulate(nums.begin(), nums.end(), 0ll);

        // 创建一个diff数组，用来存储每个元素与k进行异或运算后与原元素的差值
        vector<int> diff;

        // 遍历nums数组，对每个元素计算 (a ^ k) - a，并将结果存入diff数组
        for (auto& a : nums) {
            diff.push_back((a ^ k) - a);
        }

        // 对diff数组进行排序，确保差值从小到大排列
        sort(diff.begin(), diff.end());

        // 从diff数组的最后一个元素开始，逐对处理差值
        for (int i = diff.size() - 1; i > 0 && diff[i] + diff[i - 1] >= 0;
             i -= 2) {
            // 如果当前两项差值的和非负，则将其加到res中
            res += max(0, diff[i] + diff[i - 1]);
        }

        // 返回最终的结果res
        return res;
    }
};

// 简洁方法  dp
class Solution {
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        // 初始化两个变量 f0 和 f1
        // f0 表示不选择当前元素进行异或操作的最大值
        // f1 表示选择当前元素进行异或操作的最大值
        long long f0 = 0, f1 = LLONG_MIN;

        // 遍历nums数组中的每个元素
        for(int x : nums) {
            // 对当前元素进行计算，t 表示选择当前元素进行异或操作时的最大值
            // f1 + x 表示选择不进行异或操作时，前一个状态f1的最大值加上当前元素
            // f0 + (x ^ k) 表示进行异或操作时，前一个状态f0的最大值加上当前元素异或k后的值
            long long t = max(f1 + x, f0 + (x ^ k));

            // 更新 f0 和 f1
            // f0 为不进行异或操作时的最大值
            // f1 为进行异或操作时的最大值
            f0 = max(f0 + x, f1 + (x ^ k));
            f1 = t;
        }

        // 最终返回不选择进行异或操作的最大值（即 f0）
        return f0;
    }
};
